class Solution:
    def integerReplacement(self, n: int) -> int:
        steps = 0
        while n > 1:
            if n % 2 == 0:
                # 如果 n 是偶数，直接除以 2
                n //= 2
            else               :
                # 如果 n 是奇数，根据贪心策略选择 n + 1 或 n - 1
                if (n + 1) % 4 == 0 and n != 3:
                    n += 1
                else:
                    n -= 1
            steps += 1
        return steps


# 示例测试
solution = Solution()
print(solution.integerReplacement(7))  # 输出 4
print(solution.integerReplacement(8))  # 输出 3
print(solution.integerReplacement(4))  # 输出 2